前情提要
题目链接
成绩表
今天……行吧，刚好第10。
题解
T1
#dp
第一眼没做出来，最后做的 T1 ，一眼 DP。
然后用的方法做，结果正解发现时直接等分…… 问为啥…… 打表
还可以用，但是不是很会。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <bits/stdc++.h>
#define mod 998244353ll
#define N 2010
using namespace std;
using ll = long long;
int n, p, k;
ll f[N][110];
int main() {
freopen("per.in", "r", stdin);
freopen("per.out", "w", stdout);
scanf("%d%d%d", &n, &p, &k);
ll ans = 1;
if (n >= p) {
for (int i = 2; i <= n; ++i) {
if (i == p) continue;
ans = ans * i % mod;
}
printf("%lld", ans);
return 0;
}
f[1][0] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < p; ++j) {
for (int k = 0; k < i; ++k) {
f[i][j] += f[i - 1][((j - k) % p + p) % p];
f[i][j] %= mod;
}
}
}
printf("%lld", f[n][k]);
return 0;
}
|
T2
#贪心
这道题当时是乱搞的，我也不知道，本来想用莫队，结果后来发现不行，就用莫队暴力（其实就只排了个序……，然后就暴力），还不如暴力（悲。
正解先按 l 排序，然后从后往前，每次往前一格贪心添加就行，因为顺序其实没有关系，然后用 vector 记载一下，用一个树状数组维护尾巴的位置，查 r 就行。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<bits/stdc++.h>
#define N 500010
using namespace std;
int n, q, l, r;
char s[N];
set <int> a[6];
vector <pair<int, int> > b[N];
int tr[N], ans[N];
inline void add(int p, int v) {
while (p <= n) {
tr[p] += v;
p += (p & -p);
}
}
inline int quer(int p) {
int ans = 0;
while (p) {
ans += tr[p];
p -= (p & -p);
}
return ans;
}
int main() {
freopen("agc.in", "r", stdin);
freopen("agc.out", "w", stdout);
scanf("%d", &n);
scanf("%s", s + 1);
scanf("%d", &q);
for (int i = 0; i < q; ++i) {
scanf("%d%d", &l, &r);
b[l].emplace_back(make_pair(r, i));
}
for (int i = n; i; --i) {
if (s[i] == 'A') {
int x = i;
bool flag = 0;
for (int j = 1; j < 5; ++j) {
auto tmp = a[j].lower_bound(x);
if (tmp == a[j].end()) {
flag = 1;
break;
}
x = *tmp;
}
if (!flag) {
x = i;
for (int j = 1; j < 5; ++j) {
auto tmp = a[j].lower_bound(x);
x = *tmp;
a[j].erase(x);
}
add(x, 1);
} else {
a[0].insert(i);
}
} else {
a[s[i] - 'A'].insert(i);
}
for (auto &j : b[i]) {
ans[j.second] = quer(j.first);
}
}
for (int i = 0; i < q; ++i) {
printf("%d\n", ans[i]);
}
return 0;
}
|
T3
这道题当时是想出了方法的，（针对一个置换环） 和（针对所有置换环） 的作用也理解得很清楚，可以做一个再一个或 做最大次数。（讲不太清楚，如果看代码理解不了手玩一下就行了，前提是知道置换环，比如第个位置放，那么连接到）
求出操作的次数后枚举有多少个使用函数，显然函数找次数最多的前几个用，因为用的费用固定，的最大值肯定越小越好。
其它问题都简单，问题是求一个置换环要操作多少次？
答案是用列表（结果我也用了一个列表），然后记录每次要删的数，然后记录删的数前后的数是否能使下一个数删掉，加入一个容器，这样就能，不用每次遍历一遍。
还有就是获取置换环中的数时，可以把最大的放在开头，因为最大的肯定不会被归为，是最后被动归位的，所以可以倒着枚举置换环，更方便，不用怕数组越界。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <bits/stdc++.h>
#define N 1000010
using namespace std;
using ll = long long;
int n;
ll x, y;
int a[N];
bitset<N> vis, del;
list <int> l;
vector <list <int>::iterator> v, vv;
vector <ll> f;
int tot;
void dfs(int u) {
l.emplace_back(u);
vis[u] = 1;
if (!vis[a[u]]) dfs(a[u]);
}
void count() {
int cnt = 0;
v.clear();vv.clear();
for (auto i = next(l.begin()); i != l.end(); ++i) {
if (*prev(i) > *i) v.emplace_back(i);
}
while (l.size() > 1) {
++cnt;
vv.clear();
for (auto &i : v) {
del[*i] = 1;
}
for (int i = 0; i < v.size(); ++i) {
if (next(v[i]) != l.end() && !del[*next(v[i])] && *prev(v[i]) > *next(v[i])) {
vv.emplace_back(next(v[i]));
}
l.erase(v[i]);
}
v = vv;
}
l.clear();
f.emplace_back(cnt);
}
ll ans;
int main() {
freopen("sort.in", "r", stdin);
freopen("sort.out", "w", stdout);
scanf("%d%lld%lld", &n, &x, &y);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
for (int i = n; i; --i) {
if (!vis[i] && a[i] != i) {
++tot;
dfs(i);
count();
}
}
sort(f.begin(), f.end());
reverse(f.begin(), f.end());
ans = y * tot + x;
for (int i = 0; i < tot; ++i) {
ans = min(ans, y * i + x * f[i]);
}
printf("%lld", ans);
return 0;
}
|
后记
今天的题就是，明知道大概的方法，但是一些细节不会，悲。
